package UnionFind;

/**
 * @author chetaifu
 * 第二版Union-Find, 使用一个数组构建一棵指向父节点的树
 * parent[i]表示第一个元素所指向的父节点
 */
public class UnionFind2 {

    private int[] parent;
    private int size;

    public UnionFind2(int n){
        this.size = n;
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    /**
     * 查找元素 p 所对应的集合编号
     * 不断去查询自己的父亲节点, 直到到达根节点
     * O(h)复杂度, h为树的高度
     * */
    public int find(int p){
        assert (p >= 0 && p < size);
        while(p != parent[p]){
            p = parent[p];
        }
        return p;
    }

//    /**
//     * 递归写法
//     */
//    public int find(int p){
//        assert p >= 0 && p < size;
//        if(parent[p] == p){
//            return p;
//        }else{
//            return find(parent[p]);
//        }
//    }

    /**
     * O(h)复杂度
     * */
    public boolean isConnected(int p, int q){
        return find(p) == find(q);
    }

    /**
     * 合并元素p和元素q所属的集合
     * O(h)复杂度, h为树的高度
     */
    public void unionElement(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot == qRoot) return;
        parent[pRoot] = qRoot;
    }
}
